// https://leetcode.cn/problems/binary-search-tree-iterator/description/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用栈结构实现二叉搜索树迭代器
// 2. 构造函数初始化当前节点指针
// 3. next()方法通过中序遍历返回下一个最小元素
// 4. 遍历左子树入栈，弹出栈顶访问，转向右子树
// 5. hasNext()检查栈是否为空或当前节点是否存在
// 6. 均摊时间复杂度：O(1)，空间复杂度：O(H)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <stack>

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class BSTIterator 
{
private:
    stack<TreeNode*> st;
    TreeNode* cur;
public:
    BSTIterator(TreeNode* root) 
        :cur(root)
    {}
    
    int next() 
    {
        while (cur != nullptr)
        {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top();
        st.pop();

        int ret = cur->val;
        cur = cur->right;

        return ret;
    }
    
    bool hasNext() 
    {
        return cur != nullptr || st.empty() == false;
    }
};

TreeNode* createTestBST() 
{
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(8);
    return root;
}

void deleteTree(TreeNode* root) 
{
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main() 
{
    TreeNode* root = createTestBST();
    
    BSTIterator it(root);
    
    cout << "二叉搜索树的中序遍历结果：" << endl;
    
    // 使用迭代器遍历二叉树
    while (it.hasNext()) 
    {
        cout << it.next() << " ";
    }
    cout << endl;
    
    // 清理内存
    deleteTree(root);
    
    return 0;
}